package leetcode.array.remove;


import java.util.Arrays;

/**
 * 26. 删除有序数组中的重复项
 */
public class RemoveDuplicates {
    public static void main(String[] args) {
        RemoveDuplicates solution = new RemoveDuplicates();

        int[] nums = {1, 2, 2, 2, 4, 4, 6, 6};
        int len = solution.removeDuplicates(nums);
        System.out.println(len);
        System.out.println(Arrays.toString(nums));
    }


    /**
     * 使用快慢指针进行覆盖
     */
    public int removeDuplicates(int[] nums) {
        int left = 0;
        int right = 0;

        while (right < nums.length) {
            if (nums[left] == nums[right]) {
                right++;
            } else {
                nums[left + 1] = nums[right];
                left++;
            }
        }
        return left + 1;
    }


    /**
     * 使用双指针(自己写的)
     *
     * @param nums 数组
     * @return 不重复数组的长度
     */
    public int removeDuplicates0(int[] nums) {
        int len = nums.length;
        int second = 0;
        int first = 0;
        while (second < len - 1) {
            while (nums[second] == nums[first]) {
                second++;
                if (second > len - 1) {
                    break;
                }
            }
            if (second > len - 1) {
                break;
            }
            first++;
            nums[first] = nums[second];
        }
        return first + 1;
    }


    /**
     * 使用双指针(快慢指针)
     * 官方写法 更加简洁
     * <p>
     * 基本思路
     * 1 比较 p和 q位置的元素是否相等
     * 2 如果相等, q后移 1位
     * 3 如果不相等, 将 q位置的元素复制到 p+1位置上, p后移一位, q后移一位
     * 4 重复上述过程, 直到 q等于数组长度
     *
     * @param nums 有序数组
     * @return
     */
    public int removeDuplicates1(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int fast = 1, slow = 1;
        while (fast < n) {
            if (nums[fast] != nums[fast - 1]) {
                // 数组指定位置元素覆盖
                nums[slow] = nums[fast];
                ++slow;
            }
            // 快指针后移一位
            ++fast;
        }
        return slow;
    }

}
